package com.hqq.leetcode.tree;

import com.hqq.exercise.tree.TreeNode;

import java.util.Stack;

/**
 * IdenticalTree 相同二叉树
 * Description:
 * Check if two binary trees are identical.
 * Identical means the two binary trees have the same structure and every identical position has the same value.
 * Input:
 * ----1             1
 * ---/ \           / \
 * --2   2   and   2   2
 * -/             /
 * 4             4
 * <p>
 * ----1             1
 * ---/ \           / \
 * --2   3   and   2   3
 * -/               \
 * 4                 4
 * <p>
 * Output:
 * True
 * False
 * <p>
 * Created by heqianqian on 2017/9/13.
 */
public class IdenticalTree {

    public static void main(String[] args) {
        TreeNode tree1 = new TreeNode(1);
        TreeNode l1 = new TreeNode(2);
        l1.left = new TreeNode(4);
        tree1.left = l1;
        tree1.right = new TreeNode(2);

        TreeNode tree2 = new TreeNode(1);
        TreeNode l2 = new TreeNode(2);
        l2.left = new TreeNode(4);
        tree2.left = l2;
        tree2.right = new TreeNode(2);

        TreeNode tree3 = new TreeNode(1);
        TreeNode l3 = new TreeNode(2);
        l3.left = new TreeNode(4);
        tree3.left = l3;
        tree3.right = new TreeNode(3);

        TreeNode tree4 = new TreeNode(1);
        TreeNode l4 = new TreeNode(2);
        l4.right = new TreeNode(4);
        tree4.left = l4;
        tree4.right = new TreeNode(3);

        IdenticalTree it = new IdenticalTree();
        System.out.println(it.isIdentical(tree1, tree2));
        System.out.println(it.isIdentical(tree3, tree4));
    }

    /*
   * @param a: the root of binary tree a.
   * @param b: the root of binary tree b.
   * @return: true if they are identical, or false.
   */
    public boolean isIdentical(TreeNode a, TreeNode b) {
        // write your code here
        //return isIdenticalRecursion(a, b);
        return isIdenticalPreOrder(a,b);
    }

    private boolean isIdenticalRecursion(TreeNode a, TreeNode b) {
        if (a == null && b == null) {
            return true;
        }
        if ((a == null && b != null) || (a != null && b == null) || (a.val != b.val)) {
            return false;
        }
        return isIdenticalRecursion(a.left, b.left) && isIdenticalRecursion(a.right, b.right);
    }

    private boolean isIdenticalPreOrder(TreeNode a, TreeNode b) {
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack1.push(a);
        stack2.push(b);
        while (!stack1.empty() && !stack2.empty()) {
            TreeNode tmp1 = stack1.pop();
            TreeNode tmp2 = stack2.pop();
            if (tmp1.val!=tmp2.val){
                return false;
            }
            if (tmp1.right!=null){
                stack1.push(tmp1.right);
            }
            if (tmp2.right!=null){
                stack2.push(tmp2.right);
            }
            if (stack1.size()!=stack2.size()){
                return false;
            }
            if (tmp1.left!=null){
                stack1.push(tmp1.left);
            }
            if (tmp2.left!=null){
                stack2.push(tmp2.left);
            }
            if (stack1.size()!=stack2.size()){
                return false;
            }
        }
        return stack1.size() == stack2.size();
    }
}
